package edu.ahut.ssm;

import java.util.Arrays;

public class DynamicProgramming {

    public static final int N = 100;
    static int[] F = new int[N + 1];

    static int fib(int n) {
        if (F[n] != 0) { //先查表 如果表中已经有答案，直接读取答案 O(1)
            return F[n];
        }
        if (n <= 2) return F[n] = 1;//完成这次计算后，要及时把答案写入存储数组中
        return F[n] = fib(n - 1) + fib(n - 2);//完成这次计算后，要及时把答案写入存储数组中

    }

    public static void main(String[] args) {

//        F[1]=F[2]=1;
//        for(int i=3;i<=N;i++){
//            F[i]=F[i-1]+F[i-2];
//        }
        System.out.println("F=" + Arrays.toString(F)); //没有训练的记忆体
        fib(3);//进行了计算fib(3)
        System.out.println("F=" + Arrays.toString(F)); //没有训练的记忆体
        fib(2);//这个问题是小问题了
        System.out.println("F=" + Arrays.toString(F)); //没有训练的记忆体
        fib(4);//遇到了一个难题，存储可以辅助计算 ，计算完毕后增加新的知识
        System.out.println("F=" + Arrays.toString(F)); //没有训练的记忆体
    }
}
